package Algorithm.Dp;

public class Leetcode673 {
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
            int[] lp = new int[nums.length];



            int max = dp[0];
            int maxl = 0;


            for(int i=0;i<nums.length;i++){
                dp[i] = 1;
                lp[i] = 1;
                for(int j=0;j<i;j++){
                    if(nums[i]>nums[j]){
                        if(dp[i]<dp[j]+1){
                            dp[i] = dp[j] + 1;
                            lp[i] = lp[j];
                        }else if(dp[i] == dp[j] + 1){
                            lp[i] = lp[i] + lp[j];
                        }
                    }
                }

                if(dp[i]>max){
                    max = dp[i];
                    maxl = lp[i];
                }else if(dp[i]==max){
                    maxl += lp[i];
                }
            }
            return maxl;
        }
    }
}
